package com.zleetcode.回溯;

import java.util.ArrayList;
import java.util.List;

public class _51_N皇后 {

    // 索引表示行号，值表示列号：cols[4] = 5。  4行5列格子摆放皇后
    int[] cols;
    // 一共有多少种合理的摆法
    int ways = 0;

    List<List<String>> queens;

    public List<List<String>> solveNQueens(int n) {
        return placeQueens(4);
    }

    /**
     * n皇后, 摆放所有皇后
     */
    private List<List<String>> placeQueens(int n) {
        if (n < 1) return null;
        queens = new ArrayList<>();
        cols = new int[n];
        place(0);
        return queens;
    }

    /**
     * 从第 row 行开始摆放皇后
     */
    void place(int row) {
        if (row == cols.length) {
            // 存储这一次扫描的方法
            ways++;
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            // 判断合法性
            if (isValid(row, col)) {
                // row 行号，cols[row] = col表示在
                cols[row] = col;
                // 遍历下一行
                place(row + 1);
            }
        }
    }

    // row 行，col列的格子是否合法
    boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (cols[row] == col) return false;// 说明这一列已经存在皇后了
            // 判断对角线
            if (row - i == Math.abs((cols[i] - col))) return false;
        }
        return true;
    }

    // 使用 List 存储
    void save() {

    }
}
